{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Neighboring Bitwise XOR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: doesValidArrayExist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #相邻值的按位异或"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的数组 <code>derived</code> 是由同样长度为 <code>n</code> 的原始 <strong>二进制数组</strong> <code>original</code> 通过计算相邻值的 <strong>按位异或（⊕）</strong>派生而来。</p>\n",
    "\n",
    "<p>特别地，对于范围&nbsp;<code>[0, n - 1]</code> 内的每个下标 <code>i</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>i = n - 1</code> ，那么 <code>derived[i] = original[i] ⊕ original[0]</code></li>\n",
    "\t<li>否则 <code>derived[i] = original[i] ⊕ original[i + 1]</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组 <code>derived</code> ，请判断是否存在一个能够派生得到 <code>derived</code> 的 <strong>有效原始二进制数组</strong> <code>original</code> 。</p>\n",
    "\n",
    "<p>如果存在满足要求的原始二进制数组，返回 <em><strong>true</strong> </em>；否则，返回<em> <strong>false</strong> </em>。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二进制数组是仅由 <strong>0</strong> 和 <strong>1</strong> 组成的数组。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>derived = [1,1,0]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>能够派生得到 [1,1,0] 的有效原始二进制数组是 [0,1,0] ：\n",
    "derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1 \n",
    "derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1\n",
    "derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>derived = [1,1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>能够派生得到 [1,1] 的有效原始二进制数组是 [0,1] ：\n",
    "derived[0] = original[0] ⊕ original[1] = 1\n",
    "derived[1] = original[1] ⊕ original[0] = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>derived = [1,0]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在能够派生得到 [1,0] 的有效原始二进制数组。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == derived.length</code></li>\n",
    "\t<li><code>1 &lt;= n&nbsp;&lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>derived</code> 中的值不是 <strong>0</strong> 就是 <strong>1</strong> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [neighboring-bitwise-xor](https://leetcode.cn/problems/neighboring-bitwise-xor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [neighboring-bitwise-xor](https://leetcode.cn/problems/neighboring-bitwise-xor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,1,0]', '[1,1]', '[1,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, a: List[int]) -> bool:\n",
    "        b = 0\n",
    "        for x in a:\n",
    "            b ^= x\n",
    "        return b==0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        l = len(derived)\n",
    "        if l == 1:\n",
    "            return True if derived[0] == 0 else False\n",
    "        cur = first = 1\n",
    "        for i in range(l):\n",
    "            cur = 0 if cur == derived[i] else 1\n",
    "        return cur == first\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(lambda x,y:x^y, derived) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "    \n",
    "        last = 0\n",
    "       \n",
    "        for x in derived:\n",
    "            last ^= x\n",
    "       \n",
    "        return last == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return not derived.count(1) & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        result = 0\n",
    "        for d in derived:\n",
    "            result = result ^ d \n",
    "        return result == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "      q=[1]  \n",
    "      for x in derived:\n",
    "         if x:\n",
    "           q.append(abs(1-q[-1]))\n",
    "         else:\n",
    "           q.append(q[-1])\n",
    "      return q[-1]==q[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return not derived.count(1) & 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        # 一个数组的第一个数，是ori[0]^ori[1]\n",
    "        # 一个数组的最后一个数，是ori[0]^ori[-1]\n",
    "        # 假设ori[0] = 0\n",
    "        ori_init = 0 \n",
    "        ori_next = ori_init ^ derived[0]\n",
    "        for d in derived[1:]:\n",
    "            ori_next = d ^ ori_next\n",
    "        \n",
    "        if ori_init==ori_next:\n",
    "            return True \n",
    "        ori_init = 1 \n",
    "        ori_next = ori_init ^ derived[0]\n",
    "        for d in derived[1:]:\n",
    "            ori_next = d ^ ori_next\n",
    "        \n",
    "        if ori_init==ori_next:\n",
    "            return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return derived.count(1) % 2 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        cnt=Counter(derived)\n",
    "        if cnt[1]%2:\n",
    "            return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        a=0\n",
    "        for  i in derived:\n",
    "            a^=i\n",
    "        return a==0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        if derived is None or len(derived) == 0:\n",
    "            True\n",
    "        \n",
    "        # if len(derived) == 1:\n",
    "        #     return derived[0] == 0\n",
    "\n",
    "        # next_val = 1\n",
    "        # for i in range(len(derived)):\n",
    "        #     next_val ^= derived[i]\n",
    "        \n",
    "        # return next_val == 1\n",
    "\n",
    "        val = 0\n",
    "        for i in range(len(derived)):\n",
    "            val ^= derived[i]\n",
    "        \n",
    "        return val == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        n, cur = len(derived), 0\n",
    "        for i in range(n):\n",
    "            cur ^= derived[i]\n",
    "        return cur == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return sum(derived) & 1 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        n = len(derived)\n",
    "        def  dfs(x: int) -> bool:\n",
    "            original = [x] * n\n",
    "            for i in range(1, n):\n",
    "                original[i] = derived[i - 1] ^ original[i - 1]\n",
    "            return original[n - 1] ^ x == derived[n - 1]\n",
    "        return dfs(0) or dfs(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        ans = 0\n",
    "        for num in derived:\n",
    "            ans ^= num\n",
    "        return ans == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        n = len(derived)\n",
    "        if n == 1:\n",
    "            return derived[0] == 0\n",
    "        f1, f2 = 0, 1\n",
    "        for i in range(n - 1):\n",
    "            if derived[i] == 1:\n",
    "                f1 ^= 1\n",
    "                f2 ^= 1\n",
    "        return f1 ^ 0 == derived[-1] or f2 ^ 1 == derived[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        result = 0\n",
    "        for d in derived:\n",
    "            result = result ^ d \n",
    "        return result == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        i = 0\n",
    "        n = len(derived)\n",
    "        for j in range(n):\n",
    "            i = i^derived[j]\n",
    "\n",
    "        return not i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return derived.count(1) & 1 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(operator.xor,derived) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        c=True\n",
    "        for x in derived:\n",
    "            if x==1:\n",
    "                c=not c\n",
    "        return c \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return not reduce(xor, derived, 0) or bool(reduce(xor, derived, 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        n = len(derived)\n",
    "        dp = [1]\n",
    "        for i in range(n - 1):\n",
    "            dp.append(derived[i] ^ dp[i])\n",
    "        if dp[-1] ^ derived[-1] == dp[0]:\n",
    "            return True\n",
    "        # print(dp)\n",
    "        dp = [0]\n",
    "        for i in range(n - 1):\n",
    "            dp.append(derived[i] ^ dp[i])\n",
    "        if dp[-1] ^ derived[-1] == dp[0]:\n",
    "            return True\n",
    "        # print(dp)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return not reduce(xor, derived)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return 0 == reduce(xor, derived)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "      q=[1]  \n",
    "      for x in derived:\n",
    "         if x:\n",
    "           q.append(abs(1-q[-1]))\n",
    "         else:\n",
    "           q.append(q[-1])\n",
    "      return q[-1]==q[0]            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        n = len(derived)\n",
    "        if n == 1:\n",
    "            return derived[0] == 0\n",
    "        f1, f2 = 0, 1\n",
    "        for i in range(n):\n",
    "            if i == n - 1:\n",
    "                if f1 ^ 0 == derived[-1] or f2 ^ 1 == derived[-1]:\n",
    "                    return True\n",
    "            if derived[i] == 1:\n",
    "                f1 ^= 1\n",
    "                f2 ^= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return sum(derived) & 1 == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        t = True\n",
    "        for i in derived:\n",
    "            if i:\n",
    "                t = not t\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return not bool(sum(derived) & 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        n = len(derived)\n",
    "        ans = 0\n",
    "        for x in derived:\n",
    "            ans ^=x\n",
    "        return ans == 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        # orig[0][1] -- orig[n-1][0]\n",
    "        # derive[0] ----- derive[n-1]\n",
    "        # 0 1 1 2 2 3 ... n-1 0\n",
    "        # ^^^^^ n-1\n",
    "        # 0 1 | 1 2 2 3 ....[n-2 n-1] [n-1 0]\n",
    "        # ^^^^^ 0 ^ n-1\n",
    "        # ^^^^^ 0 ^ 1\n",
    "        ans = 0\n",
    "        for i in derived:\n",
    "            ans ^= i\n",
    "        return ans == 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        n = len(derived)\n",
    "        for val in [0, 1]:\n",
    "            prev = val\n",
    "            for i in range(0, n):\n",
    "                prev ^= derived[i]\n",
    "                if i == n - 1 and prev == val:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\n",
    "        return reduce(xor, derived) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def doesValidArrayExist(self, derived: List[int]) -> bool:\r\n",
    "        return reduce(xor, derived) == 0"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
